#include <iostream>
#include <string>
#include <vector>
#include "BinaryTree.h"
using namespace std;

// 88.43 %
class Solution
{
  public:
	int pathSum(TreeNode *root, int sum)
	{
		if (root == NULL)
			return 0;
		return findPath(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
	}

  private:
	int findPath(TreeNode *node, int sum)
	{
		if (node == NULL)
			return 0;
		int res = 0;
		if (node->val == sum)
			res += 1;
		res += findPath(node->left, sum - node->val);
		res += findPath(node->right, sum - node->val);
		return res;
	}
};

int main()
{
	int arr[] = {10, 5, 3, 3, 0, 0, -2, 0, 0, 2, 0, 1, 0, 0, -3, 0, 11, 0, 0};
	int n = sizeof(arr) / sizeof(arr[0]);
	TreeNode *tree = createBinaryTree(arr, n);
	int sum = 8;
	preorderPrint(tree);
	cout << endl;
	cout << Solution().pathSum(tree, sum) << endl;
	deleteBinaryTree(tree);
	return 0;
}
